package recursion

var m = make(map[int]int)

var table map[int]*int

func climbingStairs(n int) int {
	if n <= 2 {
		return n
	}
	if val, ok := m[n]; ok {
		return val
	}

	result := climbingStairs(n-1) + climbingStairs(n-2)
	m[n] = result
	return result
}

func climbingStairs0(n int) int {
	if n <= 2 {
		return n
	}
	a, b := 1, 2
	for i := 3; i <= n; i++ {
		current := a + b
		a, b = b, current
	}
	return b
}

func findTheFinal(id int) int {
	val, ok := table[id]
	if ok && val == nil {
		return id
	}
	return findTheFinal(*val)
}
